package com.data_structure_algorithm.data_structure.tree.bin_tree;

/**
 * @Authror PABLO
 * @Date 2022/3/29 22:30
 * @Desc 二叉树
 */
public class BinaryTree {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = new Node(0, "root");//树根
        Node node1 = new Node(1, "");
        Node node2 = new Node(2, "");
        Node node3 = new Node(3, "");
        Node node4 = new Node(4, "");
        Node node5 = new Node(5, "");
        Node node6 = new Node(6, "");
        //构建树
        binaryTree.root.left = node1;
        binaryTree.root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        //先序
        //binaryTree.preOrder();

        //中序
        // binaryTree.midOrder();

        //根据id查找对应节点
        /*Node nodeById = binaryTree.findNodeById(10);
        System.out.println(nodeById != null ? nodeById.toString() : null);*/

        //Node node = binaryTree.delNode(1);
       // System.out.println(node != null ? node.toString() : null);
        binaryTree.preOrder();
    }


    //查找节点
    //前序查找
    private Node findNodeById(int id) {
        //查找根，左右
        if (root != null) {
            return root.findNodeById(id);
        } else System.out.println("tree is null");
        return null;

    }


    Node root;

    public void preOrder() {
        //根 左右
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("tree is null");
        }

    }

    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else System.out.println("tree is null");
    }

    public Node delNode(int id) {
        Node node = null;
        if (root == null) return null;
        if (root.id == id) {
            node = root;
            root = null;
            return node;
        }
        return root.delNode(id);
    }
}

class Node {
    int id;
    String name;
    Node left;
    Node right;

    //先序
    public void preOrder() {
        System.out.println(this);
        //递归回退
        if (left != null) this.left.preOrder();
        if (right != null) this.right.preOrder();

    }

    //中序
    public void midOrder() {

        //递归回退
        if (left != null) this.left.midOrder();
        System.out.println(this);
        if (right != null) this.right.midOrder();
    }

    //后序
    public void postOrder() {
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", left=" + left +
                ", right=" + right +
                '}';
    }


    //先序查找树节点
    public Node findNodeById(int id) {
        //先查找树根
        if (this.id == id) return this;
        else if (this.left != null) return this.left.findNodeById(id);
        else if (this.right != null) return this.right.findNodeById(id);
        return null;
    }

    public Node delNode(int id) {

        Node node = null;
        //左右
        if (this.left != null && this.left.id == id) {
            node = this.left;
            this.left = null;
            return node;

        }
        if (this.right != null && this.right.id == id) {
            node = this.left;
            this.right = null;
            return node;
        }
        if (this.left != null) return this.left.delNode(id);
        if (this.right != null) return this.right.delNode(id);

        return null;
    }
}
